package com.ting.test.algorithms.n;

/**
 * Created by 雷霆 on 2021/1/23.
 * <p>
 * Description：
 * 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
 * <p>
 * F(0) = 0，F(1) = 1
 * F(n) = F(n - 1) + F(n - 2)，其中 n >
 * <p>
 * 暴力递归 之所以称之为暴力 就是因为有大量的重复计算
 */
public class FBNQ {

    public static void main(String[] args) {
        int n = 54;
        int result = f2(n);
        System.out.println(result);
    }

    private static int f2(int n) {
        if (n < 0) {
            return -1;
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        int result = 0;
        int n_1 = 0;
        int n_2 = 1;
        //f(n)=f(n-1)+f(n-2)
        for (int i = 2; i <= n; i++) {
            result = n_1 + n_2;
            n_1 = n_2;
            n_2 = result;
        }
        return result;
    }

    private static int f1(int n) {
        if (n < 0) {
            return -1;
        }

        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }
        return f1(n - 1) + f1(n - 2);
    }


}
